#include <iostream>
#include <cassert>
using namespace std;

#define U uintmax_t
#define MAXN   90

U td_fib(unsigned n)
{
    static U dp[MAXN];
    if (n < 2)
        return n;
    if (dp[n - 1] == 0)
        dp[n - 1] = td_fib(n - 1);
    if (dp[n - 2] == 0)
        dp[n - 2] = td_fib(n - 2);
    return dp[n - 1] + dp[n - 2];
}
U dt_fib(unsigned n) {
    static U dp2[MAXN];
    if (dp2[n] != 0)
        return dp2[n];
    if (n < 2)
        dp2[n] = n;
    else{
        for (unsigned i = 2; i <= n; i++)
        if (dp2[i] == 0) dp2[i] = dp2[i - 1] + dp2[i - 2];
    }
    return dp2[n];
}

int main(){
    assert(dt_fib(0) == 0);
    assert(dt_fib(1) == 1);
    assert(dt_fib(2) == 1);
    assert(dt_fib(3) == 2);
    assert(td_fib(0) == 0);
    assert(td_fib(1) == 1);
    assert(td_fib(2) == 1);
    assert(td_fib(3) == 2);

    for(int i=0;i<=MAXN;i++){
        cout<<i<<" "<<dt_fib(i)<<" "<<td_fib(i)<<"\n";
    }
}
